// @algorithm @lc id=138 lang=cpp 
// @title copy-list-with-random-headinter


// #define print(...)
// #define ListNode Node
// #define parseListNode parseNode
// #define serializeListNode serializeNode
// @test([[7,null],[13,0],[11,4],[10,2],[1,0]])=[[7,null],[13,0],[11,4],[10,2],[1,0]]
// @test([[1,1],[2,1]])=[[1,1],[2,1]]
// @test([[3,null],[3,0],[3,null]])=[[3,null],[3,0],[3,null]]
// @test([])=[]
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;
        Node ans(0), *pn = &ans;
        map<Node*, list<Node*>> rd;
        while(head){
            pn->next = new Node(head->val);
            pn = pn->next;
            rd[head].push_front(pn);
            if(head->random){
                auto it = rd.find(head->random);
                if(it == rd.end())
                    it = rd.insert({head->random, {}}).first;
                it->second.push_back(pn);
            }
            head=head->next;
        }
        for(auto & r : rd)
            for(auto it=r.second.begin(); ++it!=r.second.end();)
                (*it)->random = *r.second.begin();
        return ans.next;
    }
};